package cn.fxzhang.leetcode.no00;

/**
 * 91. 解码方法
 *
 * 类型：递推
 * 题解：f(i)表示到s[i]时的解法总数，有两种情况：
 * 1）s[i]=1~9时，f(i)=f(i-1)
 * 2）s[i-1]s[i]=10-26时，f(i)+=f(i-2)
 * 3）其他，f(i)=0
 * 时间复杂度：O(N)
 * 空间复杂度：O(N)
 *
 * 提交记录(1/1)：
 * 执行用时: 1 ms, 击败了100.00%
 * 内存消耗: 36.7 MB, 击败了58.24%
 * @author 张晓帆
 * @date 2021/4/21
 */
public class P0091_Decode_Ways {

    public int numDecodings(String s) {
        int n = s.length();
        if (s.charAt(0) == '0'){
            return 0;
        }
        int[] f = new int[n];
        f[0] = 1;
        for (int i=1; i<n; i++){
            char ch = s.charAt(i);
            if ('1'<=ch && ch<='9'){
                f[i] = f[i-1];
            }
            char pre = s.charAt(i - 1);
            if (pre == '1' && '0'<=ch && ch <='9' || pre == '2' && '0'<=ch && ch <='6'){
                f[i] = f[i]+(i>=2?f[i-2]:1);
            }
            if (f[i] == 0){
                return 0;
            }
        }
        return f[n-1];
    }

}
